//
//  main.cpp
//  静态查找
//
//  Created by 刘晨 on 2018/12/19.
//  Copyright © 2018 刘晨. All rights reserved.
//

/*
 1: 顺序查找算法的实现就是在数组的第一个位置设置哨兵位置，从后往前查找，要是查找的返回值是0，就说明没有找到
 
 2: 折半查找的实现的前提是有序表，设置头和尾部，每次比较中间位置的数的大小，小就在下半部分，大就在上班部分。
 */

#include <iostream>
using namespace std;
class FInd{
private:
    int base[100];
    int length;
public:
    void setBase(int count);
    int  search(int data);//静态查找
    void sort();
    int search_bin(int data);//折半查找
    void printBase();
};
void FInd::setBase(int count){
    length = count;
    for (int i = 1; i <= length; i++) {
        cin>>base[i];
    }
}
int  FInd::search(int data){
    base[0] = data;
    for (int i = length; i >= 0; i--) {
        if(base[i] == data){
            return i;
        }
    }
    return -1;
}
int FInd::search_bin(int data){
    int high = this->length;
    int low = 1;
    int mid ;
    while(low <= high){
        mid =  (low+high)/2;
        if(base[mid] == data){
            return mid;
        }
        else if(base[mid] < data){
            low = mid+1;
        }
        else if(base[mid] > data){
            high = mid - 1;
        }
    }
    return -1;
}
void FInd::sort(){
    for (int i = 1; i <= length; i++) {
        for (int j = 1; j <= length - i; j++) {
            if(base[j] > base[j+1]){
                int temp = base[j];
                base[j] = base[j+1];
                base[j+1] = temp;
            }
        }
    }
}
void FInd:: printBase(){
    for(int i = 1;i <= length;i++){
        cout<<base[i]<<"\t";
    }
    cout<<endl;
}
int main(){
    FInd a;
    cout<<"input data\n";
    a.setBase(7);
    cout<<"static search"<<a.search(3)<<endl;
    a.sort();
    a.printBase();
    cout<<"search_bin"<<a.search_bin(3)<<endl;
    return 0;
}
